package com.sheng.leetcode.year2022.month06.day15;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/06/15
 *
 * 719. 找出第 K 小的数对距离
 *
 * 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
 * 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。
 * 返回 所有数对距离中 第 k 小的数对距离。
 *
 * 示例 1：
 *
 * 输入：nums = [1,3,1], k = 1
 * 输出：0
 * 解释：数对和对应的距离如下：
 * (1,3) -> 2
 * (1,1) -> 0
 * (3,1) -> 2
 * 距离第 1 小的数对是 (1,1) ，距离为 0 。
 * 示例 2：
 *
 * 输入：nums = [1,1,1], k = 2
 * 输出：0
 * 示例 3：
 *
 * 输入：nums = [1,6,1], k = 3
 * 输出：5
 *
 * 提示：
 *
 * n == nums.length
 * 2 <= n <= 104
 * 0 <= nums[i] <= 106
 * 1 <= k <= n * (n - 1) / 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-k-th-smallest-pair-distance
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0719 {

    @Test
    public void test01(){
//        int[] nums = {1,3,1};
//        int k = 1;
//        int[] nums = {1,1,1};
//        int k = 2;
        int[] nums = {1,6,1};
        int k = 3;
        System.out.println(new Solution().smallestDistancePair(nums, k));
    }

}
class Solution {
    public int smallestDistancePair(int[] nums, int k) {
        //超出内存限制
        int length = nums.length;
        int count = length * (length - 1) / 2;
        int[] ints = new int[count];
        int n = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                ints[n] = Math.abs(nums[i] - nums[j]);
                n++;
            }
        }
        Arrays.sort(ints);
        return ints[k - 1];
    }
}

// 1. 先将数组nums按照从大到小进行排序
// 2. 元素之间的最小差值记做 low = 0, 最大差值记做 hi = nums[nums.length-1] - nums[0]
// 则 任意两个元素的差值一定在 low 与 hi 之间。
// 3. mid = low + (hi - low) / 2.
//         1) 定义 left = 0, right = 0, 分别代表子数组的左端下标与右端下标， count 代表满足差小于等于 mid的元素对的数量
//         2）遍历 left 到 right 子数组元素，right 从 0开始计算，直到 right == nums.length 为止
//             2.1）若是 nums[right] - nums[left] <= mid, 说明一共有 right - left 个元素对满足，count += right - left;
//             2.2）若是 nums[right] - nums[left] > mid, 此时 left右移，直到 nums[right] - nums[left] <= mid 为止。
//         3）若是  count >= k ，说明差值小于等于 mid 元素对的数量大于等于 k ，则第 k 个最小距离一定小于等于 mid，此时 hi = mid;
// 若是  count < k, 说明差值小于等于 mid 元素对的数量小于k ，则第 k 个最小距离一定大于 mid，此时 low = mid + 1;
//4. 重复 3 步，直到 low == hi 为止。
//
//class Solution {
//    public int smallestDistancePair(int[] nums, int k) {
//        Arrays.sort(nums);
//
//        int low = 0;
//        int hi = nums[nums.length - 1] - nums[0];
//
//        while (low < hi) {
//            int mid = low + (hi - low) / 2;
//            int left = 0;
//            int count = 0;
//            for (int right = 0; right < nums.length; right++) {
//                while (nums[right] - nums[left] > mid) left++;
//                count += right - left;
//            }
//            if (count >= k) {
//                hi = mid;
//            } else {
//                low = mid + 1;
//            }
//        }
//
//        return low;
//    }
//}
//————————————————
//版权声明：本文为CSDN博主「在河之洲木水」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
//原文链接：https://blog.csdn.net/qq_33775774/article/details/124580353
